home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / jcool01.zip / N_NODE.C < prev    next >
C/C++ Source or Header  |  1992-08-20  |  8KB  |  197 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12.  
  13. #include <cool/N_Node.h>
  14.  
  15. // compare_s -- Compare function for class
  16. template <class Type, int nchild> 
  17. //##CoolN_Node<Type,nchild>::Compare CoolN_Node<Type,nchild>::compare_s = &default_CoolN_Node_compare;
  18. Boolean (*CoolN_Node<Type,nchild>::compare_s)(const Type&, const Type&) = &default_CoolN_Node_compare;
  19.  
  20.  
  21. // CoolN_Node -- Simple constructor that allocates enough storage for a vector of
  22. //           pointers to CoolN_Node objects
  23. // Input:    None
  24. // Output:   None
  25.  
  26. template <class Type, int nchild> 
  27. CoolN_Node<Type,nchild>::CoolN_Node () {
  28.   for (int i = 0; i < nchild; i++)        // For each pointer in vector
  29.     this->sub_trees[i] = NULL;            // Insure NULL pointer value
  30. }
  31.  
  32.  
  33. // CoolN_Node -- Simple constructor that allocates enough storage for a vector of
  34. //           pointers to CoolN_Node objects and assigns an initial data value
  35. // Input:    Data slot value
  36. // Output:   None
  37.  
  38. template <class Type, int nchild> 
  39. CoolN_Node<Type,nchild>::CoolN_Node(const Type& value) {
  40.   this->data = value;                // Copy initial data value
  41.   for (int i = 0; i < nchild; i++)        // For each pointer in vector
  42.     this->sub_trees[i] = NULL;            // Insure NULL pointer value
  43. }
  44.  
  45.  
  46. // CoolN_Node -- Copy constructor makes deep copy
  47. // Input:    Reference to CoolN_Node
  48. // Output:   None
  49.  
  50. template <class Type, int nchild> 
  51. CoolN_Node<Type,nchild>::CoolN_Node(const CoolN_Node<Type,nchild>& n) {
  52.   for (int i = 0; i < nchild; i++)        // For each pointer in vector
  53.     this->sub_trees[i] = copy_nodes(n.sub_trees[i]); // Deep copy of subnodes
  54.   this->data = n.data;                     // Copy data value
  55.   this->compare_s = n.compare_s;        // Set compare method
  56. }
  57.  
  58.  
  59. // ~CoolN_Node -- Destructor for the CoolN_Node<Type,nchild> class
  60. // Input:     None
  61. // Output:    None
  62.  
  63. template <class Type, int nchild> 
  64. CoolN_Node<Type,nchild>::~CoolN_Node() {
  65.   for (int i = 0; i < nchild; i++)        // For each pointer in vector
  66.     delete this->sub_trees[i];            // Invoke destructor
  67. }
  68.  
  69. // is_leaf -- Determine if node has any children
  70. // Input:     None
  71. // Output:    TRUE if no children, else FALSE
  72.  
  73. template <class Type, int nchild> 
  74. Boolean CoolN_Node<Type,nchild>::is_leaf () const {
  75.   for (int i = 0; i < nchild; i++)
  76.     if (this->sub_trees[i])
  77.       return (FALSE);
  78.   return TRUE;
  79. }
  80.  
  81.  
  82. // operator[] -- Overload the brackets operator to provide a mechanism to set
  83. //               and/or get a sub-tree pointer of a node whose zero-relative
  84. //               index is specified from left to right
  85. // Input:        Zero-relative index into vector of sub-tree pointers
  86. // Output:       Reference to a pointer value
  87.  
  88. template <class Type, int nchild> 
  89. inline /*CoolN_Node<Type,nchild>::CoolN_Node_p##*/CoolN_Node<Type,nchild>*& CoolN_Node<Type,nchild>::operator[] (int index) {
  90. #if ERROR_CHECKING
  91.   if (index >= nchild)                // If index out of range
  92.     this->index_error ("operator[]", index);    // Raise exception
  93. #endif
  94.   return (this->sub_trees[index]);
  95. }
  96.  
  97.  
  98. // operator= -- Overload the assignment operator to copy all values from one
  99. //              node object to another. This routine could potentially result
  100. //              in a complete deep copy, since for each valid sub_tree pointer,
  101. //              a new node is allocated and its sub_tree pointers copied.
  102. // Input:       Reference to CoolN_Node
  103. // Output:      Rererence to updated CoolN_Node
  104.  
  105. template <class Type, int nchild> 
  106. CoolN_Node<Type,nchild>& CoolN_Node<Type,nchild>::operator= (const CoolN_Node<Type,nchild>& n) {
  107.   for (int i = 0; i < nchild; i++) {        // Invoke destructor recursively
  108.     delete this->sub_trees[i];            // for all subnodes
  109.     this->sub_trees[i] = copy_nodes(n.sub_trees[i]); // and make new deep copy
  110.   }
  111.   this->data = n.data;                // Copy data value
  112.   return *this;                    // Return reference
  113. }
  114.  
  115.  
  116. // insert_before -- Insert sub-tree pointer to child before the specified
  117. //                  zero-relative sub-tree index (numbered from left to right)
  118. // Input:           Pointer to child node, zero-relative index
  119. // Output:          TRUE/FALSE
  120.  
  121. template <class Type, int nchild> 
  122. Boolean CoolN_Node<Type,nchild>::insert_before (CoolN_Node<Type,nchild>& n, int index) {
  123. #if ERROR_CHECKING
  124.   if (index < 0 || index >= nchild) {        // If index out of range
  125.     this->index_error ("insert_before", index);    // Raise exception
  126.     return FALSE;                // Return failure status
  127.   }
  128. #endif
  129.   for (int i = nchild-1; i > index; i--)    // For each pointer after index
  130.     this->sub_trees[i] = this->sub_trees[i-1];    // Move up one in vector
  131.   this->sub_trees[i] = &n;            // Pointer to new sub-tree
  132.   return TRUE;                    // Return success status
  133. }
  134.  
  135.  
  136. // insert_after -- Insert sub-tree pointer to child after the specified
  137. //                 zero-relative sub-tree index (numbered from left to right)
  138. // Input:          Pointer to child node, zero-relative index
  139. // Output:         TRUE/FALSE
  140.  
  141. template <class Type, int nchild> 
  142. Boolean CoolN_Node<Type,nchild>::insert_after (CoolN_Node<Type,nchild>& n, int index) {
  143. #if ERROR_CHECKING
  144.   if (index < 0 || index >= nchild) {        // If index out of range
  145.     this->index_error ("insert_after", index);    // Raise exception
  146.     return FALSE;                // Return failure status
  147.   }
  148. #endif
  149.   for (int i = nchild-1; i > index+1; i--)     // For each pointer after index
  150.     this->sub_trees[i] = this->sub_trees[i-1];    // Move up one in vector
  151.   this->sub_trees[i] = &n;            // Pointer to new sub-tree
  152.   return TRUE;                    // Return success status
  153. }
  154.  
  155.  
  156. // copy_nodes -- Copies this node and all its subnodes
  157. // Input:       pointer to node to be copied
  158. // Output:      pointer to new copy of node with all new subnodes.
  159.  
  160. template <class Type, int nchild>
  161. CoolN_Node<Type,nchild>* CoolN_Node<Type,nchild>::copy_nodes (const CoolN_Node<Type,nchild>* n) const {
  162.   if (n == NULL)                
  163.     return NULL;
  164.   CoolN_Node<Type,nchild>* new_n = new CoolN_Node<Type,nchild>; 
  165.   for (int i = 0; i < nchild; i++)        // For each pointer in vector
  166.     new_n->sub_trees[i] = copy_nodes(n->sub_trees[i]); // Deep copy of subnodes
  167.   new_n->data = n->data;                   // Copy data value
  168.   return new_n;                          // Return copied node.
  169. }
  170.  
  171.  
  172. // index_error -- Raise exception invalid index
  173. // Input:         Function name, invalid index
  174. // Output:        None
  175.  
  176. template <class Type, int nchild> 
  177. void CoolN_Node<Type,nchild>::index_error (const char* fcn, int n) {
  178.   //RAISE Error, SYM(CoolN_Node), SYM(Out_Of_Range),
  179.   printf ("CoolN_Node<%s,%d>::%s: Index %d out of range.\n", "Type", nchild, 
  180.       fcn, n);
  181.   abort ();
  182. }
  183.  
  184. // default_CoolN_Node_compare -- Default node comparison function utilizing builtin
  185. //                           less than, equal, and greater than operators
  186. // Input:                    Reference to two Type data values
  187. // Output:                   -1, 0, or 1 if less than, equal to, or greater than
  188.  
  189. template <class Type>
  190. int default_CoolN_Node_compare (const Type& v1, const Type& v2) {
  191.   if (v1 == v2)                // If data items equal
  192.     return 0;                    // Return zero
  193.   if (v1 < v2)                // If this less than data
  194.     return -1;                // Return negative one
  195.   return 1;                    // Else return positive one
  196. }
  197.